Digital halftoning is a technique employing digital image processing to produce a halftone output image from a continuous tone input image. In the digital colour image halftoning technique, a continuous tone colour image is sampled, for example with a scanner, the samples are then digitised and stored in a computer device. In a full colour system, the digitised samples or pixels can consist of independent binary representation of the colour components of an image. For example, in the well known red, green and blue system (RGB), utilised in most output displays, the digitised samples or pixels consist of three binary representations of the red, green and blue scanned colour values respectively. These binary representations typically range from 0 to 255 for each colour, thereby comprising 8 bits for each colour or 24 bits to represent one pixel.
Standard CRT type display devices are able to display each pixel with a large number of variations of each colour component of the pixel. Hence, the desirability of storing 256 possible values for each colour component of each pixel of a CRT type display. Other output devices, such as printers and certain display devices such as ferro electric liquid crystal displays are often designed to only be able to display a limited number of colours or intensity values for each output colour. Hence, when displaying an output on such devices, it is necessary to create the sensation of multilevel colours by suitably distributing the possible output colours in the output image. By way of example, as shown in FIG. 1, it will be assumed that each pixel 1 of a first example display device is able to display red, green, blue and white colour values (RGBW), with each colour value taking a totally on or totally off state. Therefore, each colour component value can display one of two colours and the total number of colours which can be displayed by such a pixel will be 2.times.2.times.2.times.2=16 colours. A second illustrative example is that of a black and white raster display device wherein each pixel can display one of two colours, either black or white.
Referring now to FIG. 2, when it is desired to display a stored image 2 on a display 3 wherein each pixel of the display 3 can only display a restricted number of colours, it is necessary to utilise a halftoning technique such as error diffusion 4 so as to convert image 2 to be displayable on display 3.
One well known method of halftoning is error diffusion. The traditional form of error diffusion was developed by Floyd and Steinberg and published in "An Adaptive Algorithm for Spatial Gray Scale" in Society for Information Display 1975 Symposium Digest of Technical Papers 1975 at page 36. Referring now to FIG. 3, the Floyd and Steinberg process will now be explained, initially with reference to the display of monochrome images. In a monochrome system, each pixel 6 of an array of pixels 7 can display either black or white. Assuming that the input image has 255 possible levels of display, a decision must be taken whether to display an on or off value. In standard error diffusion, as shown in FIG. 4, an output value of 0 or off is displayed when the input value is between 0 and 128 and an output value of 1 or on is displayed when the input value is between 128 and 255. In standard error diffusion, an error value for the current pixel e.sub.ij is derived, the error value being the difference between the input value and the chosen closest value. As illustrated in FIG. 3, portions of this error value e.sub.ij are then distributed amongst the surrounding pixels which have not, as yet, been output. Although it is known to have different schemes for distributing the error, FIG. 3 shows one such scheme whereby two eighths of the error is added to the value of pixel 8, one-eighth is added to the pixel 9, one eighth is added to the pixel 10, two eighths is added to the pixel 11, one eighth is added to the pixel 12 and one eighth is added to the pixel 13. This has the effect of spreading, or "diffusing", the error over several pixels in the output image. A comprehensive survey of the different aspects and variations of the error diffusion process is provided in the standard textbook by Ulichney entitled Digital Halftoning published in 1991 by MIT Press.
With respect to a colour output display, a first known method of error diffusion of full colour images is to error diffuse each output colour independently. Alternatively, a better method for extending error diffusion to three dimensional colour is known generally as "vector error diffusion" and is disclosed in a number of articles including (1) "Color Image Quantization for Frame Buffer Display" by Paul Heckbert, published in Computer Graphics, Volume 16, Number 3, July 1982, pages 297-304, (2) IBM Technical Disclosure Bulletin Vol. 29, No. 3, August 1986, pages 1329 to 1334, and (3) U.S. Pat. No. 5,070,413 by Sullivan et al, entitled "Color Digital Halftoning with Vector Error Diffusion".
In the vector error diffusion process, the different possible output colour values are mapped to a three dimensional colour space. The error diffusion process then proceeds by finding, for a given input value, the closest possible output value in the three dimensional colour space. A vector difference is then determined being the difference between the current input colour value and the closest possible output colour value in a three dimensional sense. This vector difference is then distributed to adjacent pixels utilising the normal Floyd and Steinberg process. With reference to the example of FIG. 1, the sixteen possible colour values of pixel 1 would be mapped into corresponding three dimensional values. Each input pixel can then be processed so as to determine the closest three dimensional value and the error distributed to adjacent pixels. This process will be further discussed hereinafter with reference to an embodiment of the present invention.
Unfortunately, it has been found that the normal error diffusion process, and three dimensional variants thereof, produce unsatisfactory results when the input image comprises video or other forms of data having motion or noise characteristics. For example, in FIG. 5, there is shown an initial arrangement for utilising a display 3, having a limited number of colours per pixel to display a television signal. One approach to such a system is to connect to a signal to a receiver 15 which is designed to filter out all signals apart from the desired television signal 16. The analog television signal 16 can then be fed to an analog to digital converter 17 where it is converted to a corresponding digital format. Unfortunately, the digital signal produced will have a certain degree of "noise" associated therewith. This image signal can then be error diffused 4 in the manner as previously described before being displayed on display 3. The television signal 16 carries images to the analog to digital converter at the normal rate, for example, 32 frames per second. Unfortunately, there is associated noise with the signal 16 which results in slight variations in the colour values of various pixels from one frame to the next. It has been found that when such a signal, with noise in it, is error diffused by error diffusion unit 4, the output of the error diffusion process is often subject to slight variations from one frame to the next which in turn results in pixel values being turned on and off at a detectible and distracting rate. This problem has been found to be particularly noticeable in regions of very slowly varying intensities and can be variously described as "sparkling noise", "dancing dots" and "twinkling ". The effect produces an area having rapidly changing individual pixel values but having a substantially constant overall colour. It will be evident to those skilled in the art that the problem will apply equally to both monochrome and full colour display output devices in which video is displayed.